import math
def Farthest_insertion(cities):
    #构造初始回路
    start_city = cities[0]
    path = [start_city]
    path_number = [start_city[2]]
    path.append(start_city)
    path_number.append(start_city[2])
    cities.remove(cities[0])
    farthest_city = max(cities,key = lambda city:distance(city,cities[0]))
    path.insert(1,farthest_city)
    path_number.insert(1,farthest_city[2])
    cities.remove(farthest_city)

    # 依次将离当前路径最远的点插入到路径中
    while cities:
        farthest_city = max(cities,key = lambda x:farthest_distance(x,path))
        nearest_neighbor = path_distance(farthest_city,path)
        path.insert(nearest_neighbor,farthest_city)
        path_number.insert(nearest_neighbor,farthest_city[2])
        cities.remove(farthest_city)
    return path,path_number

#欧式距离
def distance(city1, city2):
    return math.sqrt((city1[0]-city2[0])**2 + (city1[1]-city2[1])**2)

#点与路径上各点的最远距离
def farthest_distance(city,path):
    max_distance = 0
    for i in path:
        d = distance(city,i)
        if d > max_distance:
            max_distance = d
    return max_distance

#点与路径的距离
def path_distance(city,path):
    min_distance = float('inf')
    nearest_neighbor = None
    for i in range(len(path)-1):
        d = distance(city, path[i]) + distance(city, path[i+1]) - distance(path[i], path[i+1])
        if d < min_distance:
            min_distance = d
            nearest_neighbor = i+1
    return nearest_neighbor
    